package com.hy.treeNode;

import java.util.*;

public class TreeNodeLevelOrderByRight {


    /**
     * 199.二叉树的右视图
     * 力扣题目链接
     *
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * 思路：
     *
     * 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
     *
     *      解法：队列，迭代。
     *      每次返回每层的最后一个字段即可。
     *      小优化：每层右孩子先入队。代码略。
     */

    public List<List<Integer>> levelOrderByRight(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();

        if (root == null){
            return res;
        }
        queue.offerLast(root);
        while (!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {

                TreeNode node = queue.pollFirst();

                if (node.left != null){
                    queue.addLast(node.left);
                }

                if (node.right  != null){
                    queue.addLast(node.right);
                }
                //  判断是否遍历到单层的最后面的元素（右子树）
                if (i  == len -1){
                    temp.add(node.val);
                }
            }
            res.add(temp);
        }
        return res;
    }



    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeLevelOrderByRight treeNodeLevelOrder = new TreeNodeLevelOrderByRight();
        System.out.println("层序遍历: "+treeNodeLevelOrder.levelOrderByRight(root));
    }
}
